package sorting;

/**
 * Selection Sort
 * i=0
 * [4, 9, -1, 5, 2, 7]
 * i=1
 * [-1, 9, 4, 5, 2, 7]
 * i=2
 * [-1, 2, 4, 5, 9, 7]
 * i=4
 * [-1, 2, 4, 5, 9, 7]
 * i=5
 * [-1, 2, 4, 5, 9, 7]
 * i=6
 * [-1, 2, 4, 5, 7, 9]
 * 
 * @author SamuelSantos
 *
 * @param <T>
 */
public class SelectionSort<T extends Comparable<T>>  implements Sorting<T> {

	@Override
	public void sort(T[] array) {
		for (int i=0; i < array.length; i++){
			int index = smallest(i, array);
			Util.swap(array, i, index);
		}
	}
	
	private int smallest(int beginIndex, T[] array){
		int smallestIndex = beginIndex;
		
		for (int i=beginIndex + 1; i < array.length; i++ ){
			if (array[i].compareTo(array[smallestIndex]) < 0){
				smallestIndex = i;
			}
		}
		return smallestIndex;
	}

}






















